\documentclass{article}
\usepackage{fullpage}
\usepackage{graphicx}
\usepackage{subfigure}
\usepackage{amsmath}
\usepackage{mathsymb}

\newcommand{\commentv}[1]{{\bf **Victor: #1**}}



\newtheorem{theorem}{Theorem}
\newtheorem{lemma}{Lemma}
\newtheorem{corollary}{Corollary}
\newtheorem{fact}{Fact}
\newtheorem{property}{Property}
\newtheorem{proposition}{Proposition}
\newtheorem{definition}{Definition}
\newtheorem{observation}{Observation}

\newenvironment{proof}[1][Proof]{\begin{trivlist}
\item[\hskip \labelsep {\bfseries #1}]}{\end{trivlist}}
%\newenvironment{definition}[1][Definition]{\begin{trivlist}
%\item[\hskip \labelsep {\bfseries #1}]}{\end{trivlist}}
\newenvironment{example}[1][Example]{\begin{trivlist}
\item[\hskip \labelsep {\bfseries #1}]}{\end{trivlist}}
\newenvironment{remark}[1][Remark]{\begin{trivlist}
\item[\hskip \labelsep {\bfseries #1}]}{\end{trivlist}}
\newenvironment{conjecture}[1][Conjecture]{\begin{trivlist}
\item[\hskip \labelsep {\bfseries #1}]}{\end{trivlist}}

\newcommand{\qed}{\hfill \ensuremath{\Box}}

\newcommand{\nb}[1]{\text{\emph{next($#1$)}}}
%\newcommand{\ep}[1]{\ensuremath{\hat{#1}}}

\newcommand{\boxedfig}[1]{
\begin{figure}[ht]
\framebox[\textwidth]{
\parbox{.9\textwidth}{
\centering
%\vspace*{-\baselineskip}
#1
}}
\end{figure}
}



\begin{document}

\section{Model (Victor)}
see complementarities/modelterminal

We consider games of incomplete information with continuous type spaces and finite action spaces. We follow the independent private value model with symmetric players. Each player draws his type independently from a commonly known atomless distribution $F$ over the continuous set of possible types $\Theta$. An identical finite set of actions $A$ is available to each player. Utility of player $i$ depends only on his type, his action, and actions of the other players $u: \Theta \times A^n \to \R$. Formally, the game is a tuple $\Gamma = \langle n,A,u,\Theta,F \rangle$.

Pure strategy of a player is a function that maps his type to an action $s:\Theta \to A$. Let a random variable $T$ denote the types of the other players. The expected utility of a player with type $\theta$ when playing action $a$ is $E_{T}[u(\theta,a,s(T))]$ or equivalently, $E_{s(T)}[u(\theta,a,s(T))]$. For computational reasons, we prefer the latter as there is a finite number of action profiles $s(T)$ while there is a continuum of type profiles $T$.

A symmetric pure strategy Bayesian Nash equilibrium (BNE) of the game $\Gamma$ is a strategy that maximizes the expected utility for each of player's types when the other players follow this strategy.
\begin{definition}
The strategy $s$ is a symmetric pure strategy BNE if
\begin{align}
& E_{s(T)}[u(\theta,s(\theta),s(T))] \ge E_{s(T)}[u(\theta,a,s(T))] \quad \forall\ \theta \in \Theta,\ a\in A
\end{align}
\end{definition}

A symmetric pure strategy BNE is guaranteed to exist in the class of games we described~\cite{mas-colell_84}.



\section{Simultaneous Auctions Model}
Goods $\mu$ and $\nu$ are offered for sale to $n$ bidders in separate simultaneous second-price auctions. A bidder's valuation is represented as a function of a one-dimensional signal or type $\theta_i$
\begin{align*}
& v(\theta_i) = 
\begin{cases}
f_{\mu}(\theta_i) & \text{if good $\mu$ is won}\\
f_y(\theta_i) & \text{if good $\nu$ is won}\\
f_{\mu\nu}(\theta_i) & \text{if goods $\mu$ and $\nu$ are won}
\end{cases}
\end{align*}


We assume that the functions $f_{\mu}$, $f_{\mu}$, and $f_{\mu\nu}$ are linear
\begin{align*}
& v(\theta_i) = 
\begin{cases}
\alpha_1\theta_i + \alpha_2& \text{if good $\mu$ is won}\\
\beta_1\theta_i + \beta_2 & \text{if good $\nu$ is won}\\
\gamma_1\theta_i + \gamma_2 & \text{if goods $\mu$ and $\nu$ are won}
\end{cases}
\end{align*}

%{\em should we use this model instead?}

We further assume that the constant term is zero
\begin{align*}
& v(\theta_i) = 
\begin{cases}
\alpha\theta_i & \text{if good $\mu$ is won}\\
\beta\theta_i & \text{if good $\nu$ is won}\\
\gamma\theta_i & \text{if goods $\mu$ and $\nu$ are won}
\end{cases}
\end{align*}

The model is flexible enough to describe any situation from pure complements to pure substitutes. 
For example, the values $\alpha=\beta=\gamma=1$ correspond to the pure substitutes case; $\alpha=\beta=0$ and $\gamma=1$ represent the case when $\mu$ and $\nu$ are pure complements; $\gamma=\alpha+\beta$ are for the case when $\mu$ and $\nu$ are independent; $\beta=2\alpha$ and $2\alpha \le \gamma \le 3\alpha$ model the case when good $\nu$ is twice as valuable as good $\mu$ and goods $\mu$ and $\nu$ exhibit some substitutability. The last case could arise when the same good is sold in two different quantities (e.g., 1-liter and 2-liter cartons of milk) but both goods is more than a bidder needs.

The parameters $\alpha$, $\beta$, and $\gamma$ are common knowledge; i.e. the degree of substitutability of the items is the same for all bidders. 
%A bidder's private signal $\theta$ determines how much the bidder values the goods but does not affect the substitutability structure. 

The signal $\theta_i$ is sampled from a continuous distribution.
%with the cumulative distribution function $F$ and probability density function $f$. 
The set of actions available to each bidder is given by bid pairs $b = (b_{\mu},b_{\nu}) \in B_{\mu} \times B_{\nu}$. We assume the bidders are risk-neutral and possess quasilinear utilities.

The bidders in our model are symmetric and we focus on finding symmetric equilibria. In a symmetric equilibrium, all bidders follow the same strategy. For each possible type, the strategy specifies a bid pair $b=(b_{\mu},b_{\nu})$. The strategy of a bidder induces a distribution over bid pairs  $F_{\mu\nu}(b) = \Pr(B_{\mu} < b_{\mu} \cap B_{\nu} < b_{\nu})$, where $B_{\mu}$ is a random variable representing the bid placed by a bidder on good $\mu$. Note that the inequalities comparing $B$ and $b$ are strict. We use $f$ to denote the probability that $B=b$: $f_{\mu\nu}(b) = \Pr(B_{\mu} = b_{\mu} \cap B_{\nu} = b_{\nu})$. The distribution of the first-order statistic of bid pairs (i.e., the maximum bid in each auction) of $n-1$ bidders is $G_{\mu\nu}(b) = F_{\mu\nu}(b)^{n-1}$.%and the corresponding marginal distributions are $\Pr(\mu)^{n-1}$ and $\Pr(\nu)^{n-1}$. 




The bid space is discrete and ties will arise. Our tie breaking rule is to flip a fair coin with the number of sides equal to the number of tying bidders. It is convenient to define the events that deal with ties explicitly. Consider the following possibilities when facing another bidder:
\begin{enumerate}
\item $\Pr(B_{\mu} = b_{\mu} \cap B_{\nu} < b_{\nu})$ - tie in auction $\mu$ and win auction $\nu$. 
\item $\Pr(B_{\mu} < b_{\mu} \cap B_{\nu} = b_{\nu})$ - win auction $\mu$ and tie in auction $\nu$. 
\item $\Pr(B_{\mu} = b_{\mu} \cap B_{\nu} = b_{\nu})$ - tie in both auctions
\item $\Pr(B_{\mu} < b_{\mu} \cap B_{\nu} < b_{\nu})$ - win both auctions
\item $1-\Pr(B_{\mu} \leq b_{\mu} \cap B_{\nu} \leq b_{\nu})$ - lose both auctions
\end{enumerate}
Note that all of the above events are disjoint and need to sum up to one, always. In the following, let $x$ denote the number of bidders that correspond to event $1$, $y$ to event $2$, and $z$ to event 3. We now consider the probability of winning both auctions. Let this be referred to as $\Pr(W_\mu \cap W_\nu)$:
\begin{align*}
& \Pr(W_\mu \cap W_\nu)=\sum_{x=0}^{n-1}\sum_{y=0}^{n-1-x}\sum_{z=0}^{n-1-x-y}{n-1 \choose x}{n-1-x \choose y}{n-1-x-y \choose z}\frac{1}{x+z+1}\frac{1}{y+z+1}\cdot\\
& \Pr(B_{\mu} = b_{\mu} \cap B_{\nu} < b_{\nu})^x \Pr(B_{\mu} < b_{\mu} \cap B_{\nu} = b_{\nu})^y \Pr(B_{\mu} = b_{\mu} \cap B_{\nu} = b_{\nu})^z \Pr(B_{\mu} < b_{\mu} \cap B_{\nu} < b_{\nu})^{n-1-x-y-z}
\end{align*}
%Letting $\nb{x}$ denote the next bid above $x$ (or infinity if $x$ is the highest bid), 
Letting $\epsilon$ be any positive number that is less than the difference between any two consequtive bids, we express the probabilities in this equation throught $F_{\mu\nu}$ and $f_{\mu\nu}$
\begin{align*}
& \Pr(W_\mu \cap W_\nu)=\sum_{x=0}^{n-1}\sum_{y=0}^{n-1-x}\sum_{z=0}^{n-1-x-y}{n-1 \choose x}{n-1-x \choose y}{n-1-x-y \choose z}\frac{1}{x+z+1}\frac{1}{y+z+1}\cdot\\
%& [\Pr(B_{\mu} < \nb{b_{\mu}} \cap B_{\nu} < b_{\nu}) - \Pr(B_{\mu} < b_{\mu} \cap B_{\nu} < b_{\nu})]^x [\Pr(B_{\mu} < b_{\mu} \cap B_{\nu} < \nb{b_{\nu}}) - \Pr(B_{\mu} < b_{\mu} \cap B_{\nu} < b_{\nu})]^y \Pr(B_{\mu} = b_{\mu} \cap B_{\nu} = b_{\nu})^z \Pr(B_{\mu} < b_{\mu} \cap B_{\nu} < b_{\nu})^{n-1-x-y-z}
& [F_{\mu\nu}(b_{\mu}+\epsilon,b_{\nu}) - F_{\mu\nu}(b_{\mu},b_{\nu})]^x [F_{\mu\nu}(b_{\mu},b_{\nu}+\epsilon) - F_{\mu\nu}(b_{\mu},b_{\nu})]^y f_{\mu\nu}(b_{\mu},b_{\nu})^z F_{\mu\nu}(b_{\mu},b_{\nu})^{n-1-x-y-z}
\end{align*}

For a given bid pair $b$ and distribution of bids $F_{\mu\nu}$ we define 
\begin{itemize}
\item $S_{\mu}$ - win item $\mu$ without a tie
\item $T_{\mu}$ - win item $\mu$ after tying
\item $W_{\mu} = S_{\mu} \cup T_{\mu}$ - win item $\mu$
\end{itemize}
All events are defined analogously for winning the item $\nu$ and winning both items $\mu$ and $\nu$. We calculate the probability of each event below.
\begin{align*}
& \Pr(S_{\mu}) = F_{\mu}(b_{\mu})^{n-1}\\
& \Pr(S_{\mu\nu}) = F_{\mu\nu}(b)^{n-1}\\
& \Pr(T_{\mu}) = \sum_{x=1}^{n-1}\frac{1}{x+1}{n-1 \choose x}f_{\mu}^x(b_{\mu})F_{\mu}^{n-1-x}(b_{\mu})\\
& \Pr(W_{\mu}) = \Pr(S_{\mu}) + \Pr(T_{\mu})
%& \Pr(W_{\mu\nu}) = \Pr(S_{\mu\nu}) + \Pr(T_{\mu} \cap S_{\nu}) + \Pr(T_{\nu} \cap S_{\mu}) + \Pr(T_{\mu} \cap T_{\nu})
\end{align*}

The expected utility of an agent submitting the bid pair $b$ is%when the distribution of bid pairs of any other bidder is $P_{AB}$
\begin{align}
& u(\theta_i,b) = \theta_i \Pr[\text{win}] - E[\text{cost}] \label{eq:utsimple}\\
& u(\theta_i,b) = \theta_i \left(\alpha\Pr(W_{\mu} \cap \bar{W_{\nu}}) + \beta\Pr(W_{\nu} \cap \bar{W_{\mu}}) + \gamma\Pr(W_{\mu} \cap W_{\nu})\right)  - c(b) \nonumber\\
& =  \theta_i \left(\alpha[\Pr(W_{\mu}) - \Pr(W_{\mu} \cap W_{\nu})] + \beta[\Pr(W_{\nu}) - \Pr(W_{\mu} \cap W_{\nu})] + \gamma\Pr(W_{\mu} \cap W_{\nu})\right) - c(b) \nonumber\\
& =  \theta_i \left(\alpha\Pr(W_{\mu}) + \beta\Pr(W_{\nu})  + \Pr(W_{\mu} \cap W_{\nu})[\gamma - \alpha -\beta] \right) - c(b) \label{eq:ut}
\end{align}
where $c(b)$ denotes the expected payment. The expected payment for good $\mu$ is
\begin{align*}
& c_{\mu}(b_{\mu}) = F_{\mu}(b_{\mu})^{n-1}E[Z_{\mu}|Z_{\mu} < b_{\mu}] + \Pr(T_{\mu})\Pr(Z_{\mu}=b_{\mu})b_{\mu} = \\
& \sum_{x \in B_{\mu} \mid x < b_{\mu}}f_{\mu}(x)^{n-1}x + \Pr(T_{\mu})f_{\mu}(b_{\mu})^{n-1}b_{\mu}
%& c(b) = \Pr(\mu)E[\text{highest bid on $\mu$ among the other bidders} \mid \text{$b_{\mu}$ is the highest bid}] \\
%& + \Pr(\nu)E[\text{highest bid on $\nu$ among the other bidders} \mid \text{$b_{\nu}$ is the highest bid}]
\end{align*}
The total expected payment is 
\begin{align*}
& c(b) = c_{\mu}(b_{\mu}) + c_{\nu}(b_{\nu})
\end{align*}



\section{Characterization}
\label{sec:char}
%Under the private value model for selling a single object in a high bid auction, when bids and values are continuous, all equilibrium strategies are increasing in the bid~\ref{eqinshba00}. In fact, there is a unique symmetric equilibrium \commentv{need to find results on uniqueness of symmetric equilibria. Maskin in "Uniqueness of equilibrium in sealed high-bid
%auctions" claims "With a symmetric distribution of types, it
%is well known that there is only one symmetric equilibrium (Milgrom and Weber, 1982;
%Maskin and Riley, 1984)." Could not find the result for ind private value model in milgrom's paper.}
%%uniqueness in affiliated models is shown (krishn'a auction theory). what about private values?
%%It is well-known that in single auction equilibrium strategies, the bid increases in value\commentv{check + reference}. 
%Model with discrete bids was considered by in~\ref{discretefirstbid}.
%\commentv{list papers talking about sim auctions}
%Nobody has provided general characterization results for the setting with simultaneous auctions.
\begin{figure}
\begin{center}
\includegraphics[width=8cm]{graphs/envelope}
\end{center}
\caption{Utility lines for bids $B = \{b_1,b_2,b_3,b_4\}$ given price distribution $G$. The best-response is highlighted.\label{fig:envelope}}
\end{figure}
For a given joint distribution $G$ of the highest bids of the other agents (henceforth, {\em price distribution}), utility that agent $i$ derives from submitting a bid $b_j$ is a linear function of the private type $\theta_i$
\begin{align*}
& u(\theta_i,b_j,G) = \theta_i \Pr[\text{win}\mid b_j,G] - E[\text{cost}\mid b_j,G]
\end{align*}
The probability of winning provides the slope and the expected cost provides the intercept.
Figure~\ref{fig:envelope} illustrates utility lines for each bid an agent may submit. It is obvious from the picture that the best response of agent $i$ to price distribution $G$ is given by a piecewise linear function formalized below.
\begin{definition}
A set of bids $B' = \{b_1, \ldots, b_{m'}\}$ and an increasing vector $a \in \R^{m-1} \mid 0 \le a_1 \le \ldots \le a_{m-1} \le 1$ define a {\em piecewise linear strategy}
\begin{align*}
& s(\theta_i) = b_{j} \quad \text{if } \theta_i \in [a_{j-1},a_{j}]
\end{align*}
with the convention $a_0 = 0$ and $a_{m'} = 1$. 
\end{definition}
In Figure~\ref{fig:envelope}, the best response is a piecewise linear strategy given by $B' = \{b_1,b_3,b_4\}$, and $a_1=x$, $a_2=y$. The following lemma further characterizes the best response.
\begin{lemma}
\label{lem:ue}
Given a price distribution $G$ and possible bids $B = (b_1, \ldots, b_m)$ ordered according to the increasing slope of their utility lines, the {\em best response} is a piecewise linear strategy $(B',a)$ such that
\begin{align}
& u(a_{j},b_{\sigma(j)},G) = u(a_{j},b_{\sigma(j+1)},G) \quad \forall\ 1 \le j \le m'-1 \label{eq:ut}\\
& u(0,b_{\sigma(1)},G) \ge u(0,b_k,G) \quad \forall\   k < \sigma(1) \label{eq:utineq1}\\
& u(a_{j},b_{\sigma(j)},G) \ge u(a_{j},b_k,G) \quad \forall\ 1 \le j \le m' \quad \sigma(j) < k < \sigma(j+1) \label{eq:utineq2}
%& u(a_{j-1},b_{\sigma(j)},G) \ge u(a_{j-1},b_k,G) \quad \forall\ 1 \le j \le m' \quad \sigma(j-1) < k < \sigma(j) \label{eq:utineq1}\\ %THESE COMPARISONS ARE MADE AS PART OF PREVIOUS J!!!
\end{align}
where $B' \subseteq B$, $m' = |B'|$, $\sigma \subseteq \{1,2,\ldots, m\}$ denotes the indexes of bids $B$ that are part of $B'$,  $\sigma(m'+1) = m+1$, $a_0 = 0$, $a_{m'} = 1$, and $a \in R^{m'-1}\mid 0 \le a_1 \le \ldots \le a_{m'-1} \le 1$.
\end{lemma}
\commentv{add a proof}
The best response on the interval $[a_{j-1}, a_{j}]$ is given by the utility line $u(\cdot,b_{\sigma(j)},G)$. There is a one-to-one correspondence between bids $B'$ and intervals of the envelope. The values of $a_1, \ldots, a_{m'-1}$ are determined by Equations~\ref{eq:ut}. Equations~\ref{eq:utineq1} and~\ref{eq:utineq2} guarantee that utility lines of the bids $B \setminus B'$ are below the best-response lines.

%This definition describes the upper envelope of utility lines for bids $B$. Each of the lines on the upper envelope corresponds to a bid in $B'$. The points where best response changes from one bid to the next are $a_j$. The inequalities guarantee that no utility line is higher for any of agent's types. 


In this paper we focus on symmetric equilibria. A strategy is a symmetric equilibrium if and only if it is the best response to the price distribution resulting from the other bidders playing this strategy. Invoking Lemma~\ref{lem:ue}, we get the following corollary.
\begin{corollary}
\label{cor:symeq}
%NB: this is price distribution, not the probability of winning! so we don't need to worry about ties.
A symmetric equilibrium is a best response $(B',a)$ to the price distribution $G(\cdot;a)$ defined as follows 
\begin{align}
& h(b_{\pi(j)};a) = F(a_j)-F(a_{j-1}) \quad \forall\ 1 \le j \le |B'|\label{eq:pdf} \\
& H(b;a) = \sum_{b' \in B' \mid b' \le b} h(b';a)\label{eq:cdf}\\
& G(\cdot;a) = H^{n-1}(\cdot;a)\label{eq:Gsym}
\end{align}
%As the strategy is the best response, it has the form described in Definition~\ref{def:ue}: i.e., it is given by a set of bids $B'$ ordered according to $\pi$ and constants $a$. In any such strategy, the bid $b_{\pi(j)} \in B'$ is played only by the types $\theta_i \in [a_j, a_{j-1}]$; i.e., with the probability $F(a_j)-F(a_{j-1})$. A piecewise linear strategy is a symmetric equilibrium if is the best response to the price distribution it induces.
\end{corollary}
%The price distribution is defined by the upper-envelope strategy, which in turn is the best response to this price distribution. 
Lemma~\ref{lem:ue} and~\ref{cor:symeq} tell us that finding equilibrium is equivalent to finding a set of bids and corresponding parameters that satisfy Equations~\ref{eq:ut}-\ref{eq:Gsym}. 
A direct way of searching for an equilibrium is for each possible subset of bids $B' \subseteq B'$ to check whether there exist parameters satisfying these equations. 
%One way to search for an equilibrium is to pick an ordered set of bids $B'\subseteq B$ and solve Equations~\ref{eq:ut} where the distribution $G$ is a function of $a$. 
%The solution is valid only if $0 \le a_1 \le \ldots \le a_{|B'|} \le 1$. 
%Note, that the ordering of slopes of bids $B'$ under the price distribution defined by $a$ is the same as the original ordering of bids in $B'$ as $a$ defines an upper envelope where the bids appear in order.
The equations can be arbitrarily complex depending on the distribution of types and number of players. In the next section, we derive analytical results for 2 identical auctions with 2 possible bids per auction, 2 bidders, and a uniform distribution of types. 
%Even there analytical derivation is rather cumbersome. More general examples are hardly solvable analytically, justifying the computation approach we present in section~\ref{}.


\subsection{Two Identical Items, Two Bidders, Two Bids Per Auction, Uniform Distribution of Types}
We restrict attention to 2 auctions each selling an identical item and 2 bidders with types uniformly distribution between $0$ and $1$. The only bids that can be placed in either auction are $0$ and $1$. The set of possible joint bids is  $B = \{(0,0)\ (0,1)\ (1,0)\ (1,1)\}$. In our model, identical items are encoded by the equality $\alpha=\beta$. We assume that the highest bid is the same as the highest possible independent value of the item setting $\alpha=\beta=1$. The only remaining complementarity parameter is $\gamma$, which determines how much more or less an agent values having both items. 
%The only assumption we place of $\gamma$ is that of free disposal: $\gamma \ge 1$. 
We analytically derive equilibria as a function of $\gamma$.

Recall that a symmetric equilibrium is a best response to the distribution of prices it induces.
For the uniform distribution of types between $0$ and $1$, the price distribution in Equation~\ref{eq:pdf} induced by a piecewise linear strategy $(B',a)$ becomes
\begin{align*}
& h(b_{\pi(j)};a) = F(a_j)-F(a_{j-1}) =  a_j - a_{j-1}
\end{align*}
For case of 2 players, we have $G(\cdot,a) = H(\cdot,a)$.


We make a few observations before searching for piecewise linear strategies that constitute symmetric equilibria.
The bids $(0,1)$ and $(1,0)$ must be played with the same probability in equilibrium. Acquiring either item is isolation has the same utility for the agent. It is easy to see that if $(1,0)$ is played more often than $(0,1)$, then the probability that the second auction has the price of $0$ is higher and the best response is to bid $(0,1)$ more often. Therefore, in equilibrium, the probabilities of bidding $(1,0)$ and $(0,1)$ are the same, and these bids share the same utility line. Since the bids share the same utility line, the best response interval on which either of the bids is played is continuous. If these bids are played in an equilibrium on the interval $[a_1,a_2]$, then there is a continuum of equivalent equilibria where
\begin{align*}
& s(\theta_i) = (0,1) \text{ or } (1,0) \mid f(1,0) = f(0,1) = \frac{a_2-a_1}{2} && \text{if } \theta_i \in [a_1,a_2]
\end{align*}
%A simple equilibrium of this form is the one switching from $(1,0)$ to $(0,1)$ halfway between $a_1$ and $a_2$: i.e., setting the parameter $a_2 = a_1 + \frac{a_3-a_1}{2}$. For the sake of clarity, we focus on this particular equilibrium in our derivations and let $a_2$ be determined by $a_1$ and $a_3$. 
For convenience, since the probabilities of playing bids $(1,0)$ and $(0,1)$ are the same, we will only talk about the bid $(1,0)$.


The order of slopes of the bids is the same for all values of $\gamma$ and all price distributions: $(0,0)$ has the lowest slope, $(1,0)$ is next, and $(1,1)$ has the highest slope. It is easy to show that the bid $(0,0)$ is part of the best response to any price distribution and thus, is played with a positive probability in any equilibrium. These two observations imply that the possible sets of equilibrium bids are $(0,0)$ by itself, the bids $(0,0)$ $(1,0)$, the bids $(0,0)$ $(1,1)$ and the set of all bids.  
We derive equilibria for each of these sets.

Consider the set $B' = \{(0,0)\ (1,0)\}$ as an example. In the notation of Lemma~\ref{lem:ue}, $m' = |B'| = 2$, and we are looking for the parameter $0\le a_1 \le 1$ satisfying
%Since bid $(1,1)$ is not part of the set, the piecewise linear strategy must set $a_3=1$; and since $(0,0)$ and $(1,0)$ are part of $B'$, the strategy sets $0<a_1<1$. Parameters $a_2$ and $a_3$ are linked and $a_3=1$, we have $a_2 = a_1 + \frac{a_3-a_1}{2}$. The only degree of freedom is $a_1$ which by Lemma~\ref{lem:ue} for the set $B' = \{(0,0)\ (1,0)\}$ must satisfy
\begin{align*}
& u(a_1,(0,0),H(\cdot,a)) = u(a_1,(1,0),H(\cdot,a))\\
& u(1,(1,0),H(\cdot,a)) \ge u(1,(1,1),H(\cdot,a))
\end{align*}
These equations are quadratic in $a_1$. The system has a solution only for $0<\gamma \le 2(2 - \sqrt{2})$. The solution is unique and is given by
\begin{align*}
& a_1 = \frac{-4 - \gamma + \sqrt{16\gamma + \gamma^2}}{-4 + 2\gamma}
\end{align*}

Carrying out a similar analysis, we derive equilibria for the other 2 sets of bids. Detailed derivations can be found in the appendix. There is a unique equilibrium for each value of $\gamma$. Equilibrium as a function of $\gamma$ is plotted in Figure~\ref{fig:eq}. The probability of playing each bid is plotted as a function of $\gamma$. Since bids $(0,1)$ and $(1,0)$ have the same probability, they are plotted as one line denoting the total probability. The vertical lines separate regions where the bids in equilibrium support (appearing at the top of each region) change.
\begin{figure}
\begin{center}
\includegraphics[width=\columnwidth]{graphs/eq}
\end{center}
\caption{Equilibrium probability of playing each bid for each value of $\gamma$.\label{fig:eq}}
\end{figure}

Interestingly, equilibrium probabilities of each bid are continuous in $\gamma$. 
For low degrees of complementarity, bid $(1,1)$ is not played, bid $(0,0)$ decreases and $(1,0)$ increases. Starting from  $\gamma= 2(2 - \sqrt{2})$, the probability of playing $(0,0)$ increases while $(1,0)$ decreases rapidly. The bid $(1,0)$ is no longer played in equilibrium after $\gamma$ reaches $2$. This is when the probability of $(0,0)$ begins to decrease approaching $0$ as $\gamma$ increases. The probability of bid $(1,1)$ becomes non-zero at $\gamma= 2(2 - \sqrt{2})$ and monotonically increases approaching $1$ in the limit.

The value of $\gamma = 2$ corresponds to independent auctions and equilibrium can be found for each auction separately. The single auction equilibrium  with possible bids $0$ and $1$ can be easily derived: the unique equilibrium is to bid $0$ for the values below $.5$ and to bid $1$ for the values above $.5$. Combining individual equilibrium strategies, we get the equilibrium strategy: bid $(0,0)$ for the values below $.5$  and $(1,1)$ for the values above. Each of the two equilibrium bids has the probability of $.5$ as can be seen in Figure~\ref{fig:eq} for $\gamma=2$.


\commentv{anything general to say about uniqueness or continuity results?}


\newpage
%We were not able to prove uniqueness of equilibria for the general but the computational results suggest that it holds.

The equation holds for $\gamma \le 2(2 - \sqrt{2})$. 

\begin{align*}
& a_1 = \frac{-4 - \gamma + \sqrt{16\gamma + \gamma^2}}{-4 + 2\gamma}
\end{align*}
The equation holds for $\gamma \le 2(2 - \sqrt{2})$. 




The only solution that satisfies $0 < a_1 < 1$ is
\begin{align*}
& a_1 = \frac{-4 - \gamma + \sqrt{16\gamma + \gamma^2}}{-4 + 2\gamma}
\end{align*}
The equation holds for $\gamma \le 2(2 - \sqrt{2})$. 


First, check if there are values of $\gamma$ supporting equilibria with the bids  $B' = \{(0,0)\ (1,0)\ (0,1)\}$. Upper envelopes for $B'$ are given by $0 < a_1 < a_2 < a_3 = 1$; i.e., the only parameters are $a_1$ and $a_2$. But since parameters $a_2$ and $a_3$ are linked and $a_3=1$, we have $a_2 = a_1 + \frac{a_3-a_1}{2}$, and the only degree of freedom is $a_1$. According to Lemma~\ref{obs:symeq}, $a_1$ must satisfy
\begin{align*}
& u(a_1,b_1,H(\cdot,a)) = u(a_1,b_2,H(\cdot,a))
\end{align*}
The equation is quadratic in $a_1$ and has a unique feasible (i.e., $0 < a_1 < 1$) solution for $\gamma > 0$:
\begin{align*}
& a_1 = \frac{-4 - \gamma + \sqrt{16\gamma + \gamma^2}}{-4 + 2\gamma}
\end{align*}
In order for $B',a$ to define an equilibrium strategy, Equations~\ref{eq:utineq} must hold as well. In this case, it is sufficient to check \commentv{fix me} a single inequality
\begin{align*}
& u(1,b_2,H(\cdot,a)) \ge u(1,b_4,H(\cdot,a))
\end{align*}
The equation holds for $\gamma \le 2(2 - \sqrt{2})$. 

Now we move to equilibria that include all bids: $B' = B = \{(0,0)\ (1,0)\ (0,1)\ (1,1)\}$. The parameters $a$ describing such equilibria satisfy $0 < a_1 < a_2 < a_3 < 1$. As before, $a_2 = a_1 + \frac{a_3-a_1}{2}$, and the free parameters are $a_1$ and $a_3$ that must satisfy
\begin{align*}
& u(a_1,b_1,H(\cdot,a)) = u(a_1,b_2,H(\cdot,a)) \\
& u(a_3,b_3,H(\cdot,a)) = u(a_3,b_4,H(\cdot,a)) 
\end{align*}
This is a system of 2 quadratic equations that actually reduce to a cubic equation in $a_1$. The system has a solution in the feasible range only for $2(2 - \sqrt{2})< \gamma < 2$. and the solution is re is a unique solution in the feasible range ($0<a_1<a_3<1$) for $2(2 - \sqrt{2})< \gamma < 2$. The solution is
\begin{align*}
& a_1 = (2 (2 - 2 g + \sqrt{-g^2 + g^3}))/(4 - 4 g + g^2)
\end{align*}



Let us consider equilibria supported by the bids $B' = \{(0,0)\ (1,1)\}$. The corresponding upper envelopes are described by $0 < a_1 = a_2 = a_3 < 1$. We only need to find $a_1=a_2=a_3$: the point where the best response changes from $(0,0)$ to $(1,1)$.
By Lemma~\ref{obs:symeq}
\begin{align*}
& u(a_3,b_1,H(\cdot,a)) = u(a_3,b_4,H(\cdot,a))
\end{align*}




real root only for g > N[2 (-11 + 8 Sqrt[2])]= 0.627417
first root always negative: $a_3 = (-6 - g - \sqrt{-28 + 44 g + g^2})/(4 (-2 + g))$
%(-6 - g - Sqrt[-28 + 44 g + g^2])/(4 (-2 + g))
second root $a_3 = (-6 - g + \sqrt{-28 + 44 g + g^2})/(4 (-2 + g))$
 it's below one for 2/3 < g, and approaches zero from above as g increases


We still need to check that Equations~\ref{eq:utineq} hold. 
\commentv{explain why this is enough in the general characterization}
\begin{align*}
& u(a_3,b_1,H(\cdot,a)) \ge u(a_3,b_2,H(\cdot,a))\\
& u(a_3,b_4,H(\cdot,a)) \ge u(a_3,b_2,H(\cdot,a))
\end{align*}
%But these inequalities are equivalent as we know that (MUST WORK IN BOTH DIRECTIONS -- WHICH G'S ARE FEASIBLE: ABOVE OR BELOW -- this is ok, the equation is the same! - double check tho. - done
\begin{align*}
& u(a_3,b_1,H(\cdot,a)) = u(a_3,b_4,H(\cdot,a))
\end{align*}
We check 
\begin{align*}
& u(a_3,b_1,H(\cdot,a)) \ge u(a_3,b_2,H(\cdot,a))
\end{align*}
NB: $a$ here is the distribution defined by $u(a_3,b_1,H(\cdot,a)) = u(a_3,b_4,H(\cdot,a))$; not the same as in the case with envelop with 4 bids.

The inequality holds for $2 < gamma$ (is undefined for $\gamma ==2$ - division by zero;  negative for $2/3 \le \gamma <2$ and not real for $\gamma < 2/3$).





There is no equilibrium for $\gamma =2$. indep auctions. if g=2 then $a_3$ can be anything! TODO: solve the system of equations for g=2. actually you already did - you solved it for one auction - this is the separable case.

TRY TO UNDERSTAND WHY EVEN THOUGH, THERE COULD BE MULTIPLE EQUILIBRIA, IT DOES NOT ARISE!





start from all bids, find when they are the best response


\newpage


The system reduces to one cubic equation in $a_1$.
For the root $(2 (2 - 2 g + Sqrt[-g^2 + g^3]))/(4 - 4 g + g^2)$, the solution is in the feasible range ($0<a_1<a_3<1$) for $2(2 - \sqrt{2})< \gamma < 2$

the root $(2 (2 - 2 g - Sqrt[-g^2 + g^3]))/(4 - 4 g + g^2)$, real value only for $1\le g$, negative for all $g$. (zero for $g=1$ but the corresponding $a_3=2$).

the root $a_1 = -(4./(-2 + g))$ - negative for $g>2$. above 1 for $0<g<2$


\commentv{conjecture: adding a bid with a higher slope, has a feasible solution only for g that starts where feasible range of g for equilibria with the bid ends}



state later with all uniqueness results!! still possible that there is an equlibirum with all bids for this range of gamma. or is it not???
\begin{lemma}
For $\gamma \in [0, 2(2 - \sqrt{2})]$, there is a unique (continuum) equilibrium where  There is only one equilibrium of this form and it is given by $a_2=1$ and 
\begin{align*}
& a_1 = \frac{-4 - \gamma + \sqrt{16\gamma + \gamma^2}}{-4 + 2\gamma}
\end{align*}
\end{lemma}

When the items display enough complementarity (specifically, $\gamma > 2(2 - \sqrt{2})]$), the highest bid of $(1,1)$ is played in equilibrium.







\begin{align*}
& u(\theta_i,(0,0)) = \theta_i [\alpha(\frac{1}{4}x+\frac{1}{2}y) + \beta(\frac{1}{4}x+\frac{1}{2}y) + \gamma\frac{1}{4}x] \\
& u(\theta_i,(1,0)) = u(\theta_i,(0,1)) = \theta_i [\alpha(\frac{1}{4}y + \frac{1}{2}) + \beta\frac{1}{4}y + \gamma(\frac{1}{4}y + \frac{1}{2}x)] - \frac{1}{2}(1-x-y)\\
& u(\theta_i,(1,1)) = see appendix.tex
\end{align*}



Since we are dealing with identical auctions, the parameters $\alpha$ and $\beta$ are the same. In what follows, we set both to 1, the highest individual value of either item. The only remaining free parameter is $\gamma$.
\begin{align*}
& u(\theta_i,(0,0)) = \theta_i [\frac{1}{4}x+\frac{1}{2}y + \frac{1}{4}x+\frac{1}{2}y + \gamma\frac{1}{4}x] \\
& u(\theta_i,(1,0)) = u(\theta_i,(0,1)) = \theta_i [\frac{1}{4}y + \frac{1}{2} + \frac{1}{4}y + \gamma(\frac{1}{4}y + \frac{1}{2}x)] - \frac{1}{2}(1-x-y)\\
& u(\theta_i,(1,1)) = see appendix.tex
\end{align*}
Simplifying these equations, we obtain
\begin{align*}
& u(\theta_i,(0,0)) = \theta_i [\frac{1}{2}x+y + \gamma\frac{1}{4}x] \\
& u(\theta_i,(1,0)) = u(\theta_i,(0,1)) = \theta_i [\frac{1}{2}y + \frac{1}{2} + \gamma(\frac{1}{4}y + \frac{1}{2}x)] - \frac{1}{2}(1-x-y)\\
& u(\theta_i,(1,1)) = see appendix.tex
\end{align*}

For two bidders and values uniformly distributed between $0$ and $1$, the probabilities of playing each bid in equilibrium characterized in Figure~\ref{fig:iaeq} become
\begin{align*}
& x = a_1\\
& y = z = \frac{a_2-a_1}{2}
\end{align*}
Updating the utility equations, we get
\begin{align*}
& u(\theta_i,(0,0)) = \theta_i [\frac{1}{2}x+y + \gamma\frac{1}{4}x] \\
& u(\theta_i,(1,0)) = u(\theta_i,(0,1)) = \theta_i [\frac{1}{2}y + \frac{1}{2} + \gamma(\frac{1}{4}y + \frac{1}{2}x)] - \frac{1}{2}(1-x-y)\\
& u(\theta_i,(1,1)) = see appendix.tex
\end{align*}


According to the characterization, an equilibrium is given by two parameters $a$ and $b$. When the parameters satisfy $0<a<b<1$, all 4 bids are played with positive probabilities. 
%However, 3 special cases are possible: bid $(0,0)$ is not played when $0=a<b<1$, bids $(1,0)$ and $(0,1)$ are not played when $0<a=b<1$, and bid $(1,1)$ is not played when $0<a<b=1$
We start by considering the case when the bid $(1,1)$ is not played in equilibrium. This is the case when $0<a<b=1$. We have
%First, we consider the case where the bid $(1,1)$ is never played in equilibrium: i.e., when the sum of probabilities of playing the other bids is one
\begin{align*}
& x = a\\
& y = \frac{1-a}{2}
\end{align*}
A single parameter $a$ describes an equilibrium: the value after which it becomes optimal to change the bid from $(0,0)$ to either $(1,0)$ or $(0,1)$:
\begin{align*}
& u(a,(0,0)) = u(a,(1,0))\\
& a [\frac{1}{2}x+y + \gamma\frac{1}{4}x] = a [\frac{1}{2}y + \frac{1}{2} + \gamma(\frac{1}{4}y + \frac{1}{2}x)] - \frac{1}{2}(1-x-y)
\end{align*}
Plugging in $x=a$ and $y = \frac{1-a}{2}$ and simplifying we obtain
\begin{align}
%& x [\frac{1}{2}x+y + \gamma\frac{1}{4}x] = x[\frac{1}{2}y + \frac{1}{2} + \gamma(\frac{1}{4}y + \frac{1}{2}x)] - \frac{1}{2}(1-x-y)\\
%there is  a mistake in the following lines
%& x [\frac{1}{2}x+\frac{1-x}{2} + \gamma\frac{1}{4}x] = x[\frac{1}{2}\frac{1-x}{2} + \frac{1}{2} + \gamma(\frac{1}{4}\frac{1-x}{2} + \frac{1}{2}x)] - \frac{1}{2}(1-x-\frac{1-x}{2})\\
%& \frac{1}{4}\gamma x^2 + \frac{1}{2}x = x[\frac{3}{4} - \frac{1}{4}x + \gamma\frac{1}{8} - \gamma \frac{3}{8}x] - \frac{1}{4} +\frac{x}{4}\\
%& \frac{1}{4}\gamma x^2 + \frac{1}{2}x = \frac{3}{4}x - \frac{1}{4}x^2 + \gamma\frac{1}{8}x - \gamma \frac{3}{8}x^2 - \frac{1}{4} +\frac{x}{4}\\
%& \frac{1}{4}x^2 + \frac{5}{8}\gamma x^2 - \frac{1}{2}x - \frac{1}{8}\gamma x  + \frac{1}{4} = 0 \\
%& 2x^2 + 5\gamma x^2 - 4x - \gamma x  + 2 = 0\\
%end mistake
%&x^2(\frac{1}{3}\gamma - \frac{2}{3}) + x(\frac{4}{3}  + \frac{1}{3}\gamma) - \frac{2}{3} = 0
&a^2(\gamma - 2) + a(\gamma + 4) - 2 = 0 \label{eq:quad}
\end{align}
For an  equilibrium with the bids $(0,0)$, $(1,0)$, and $(0,1)$ to exist, the equation must have a solution between 0 and 1.
This quadratic equation has at least one solution when
\begin{align*}
&(\gamma + 4)^2  + 8(\gamma - 2) \ge 0
\end{align*}
i.e., when $\gamma \le -16$ or $\gamma \ge 0$. A natural free disposal condition corresponds to $\gamma \ge 1$. So a solution exists for all values of $\gamma$ satisfying free disposal. Value of $\gamma$ between $0$ and $1$ mean that the value when both items are won is less than the value when only 1 item it won. Negative values of $\gamma$ mean that winning both items has negative utility for the bidders. As this case is rather unrealistic, we assume $\gamma \ge 0$.

Two roots of Equation~\ref{eq:quad} are 
\begin{align*}
& a_1 = \frac{-4 - \gamma - \sqrt{16\gamma + \gamma^2}}{-4 + 2\gamma} \\
& a_2 = \frac{-4 - \gamma + \sqrt{16\gamma + \gamma^2}}{-4 + 2\gamma}
\end{align*}
%The root $a_1 \notin [0,1]$
The root $a_1$ is either below 0 or above 1 for all values of $\gamma$. The other root $a_2$ is strictly above $0$ and below $1$: i.e., in the valid range for the parameter $a$. Thus, it specifies a possible equilibrium given by $b=1$ and 
\begin{align*}
& a = a_2 = \frac{-4 - \gamma + \sqrt{16\gamma + \gamma^2}}{-4 + 2\gamma}
\end{align*}
%with the corresponding distribution of bids
%\begin{align*}
%& x = a\\
%& y = z = \frac{1-a}{2}
%\end{align*}
This is an equilibrium if there is no type for which the bid $(1,1)$ yields the highest utility when the distribution of bids is $x=a,y=z=\frac{1-a}{2}$. 
%Next, we find the values of $\gamma$ for which this is the case.
Recall that the slope of $(1,1)$ is the steepest and, therefore, it achieves the highest utility relative to the other bids at the highest possible type $\theta_i=1$. To make sure that $(1,1)$ is never the best bid, we only need to check that the utility from bidding $(1,1)$ is lower than the utility from playing the bid with the next highest slope at $\theta_i=1$. 
%The utility of bidding $(1,1)$ depends the distribution of bids, specifically on $x$ and $y$. Fortunately we have a closed-form solution for $x$ and $y$. 
\begin{align*}
& u(1,(1,0)) - u(1,(1,1)) \ge 0\\
& \frac{1}{2}y + \frac{1}{2} + \gamma(\frac{1}{4}y + \frac{1}{2}x) - \frac{1}{2}(1-x-y) - \left(-\frac{1}{2}x+ 2y + \frac{1}{2} + \gamma(\frac{3}{4}x -\frac{1}{2}y + \frac{1}{4}) - 1 + x + y \right) \ge 0
\end{align*}
After simple manipulations we get
\begin{align*}
& \frac{16 - 24 \gamma + 5 \gamma^2 + \gamma^{\frac{3}{2}}\sqrt{16 + \gamma}}{32 - 16 \gamma} \ge 0
\end{align*}
which holds for $\gamma \le 2(2 - \sqrt{2})$. We have the following lemma.

\begin{lemma}
An equilibrium where only bids $(0,0)$, $(1,0)$, $(0,1)$ are played exists for $\gamma \in [0, 2(2 - \sqrt{2})]$. There is only one equilibrium of this form and it is given by $a_2=1$ and 
\begin{align*}
& a_1 = \frac{-4 - \gamma + \sqrt{16\gamma + \gamma^2}}{-4 + 2\gamma}
\end{align*}
\end{lemma}

When the items display enough complementarity (specifically, $\gamma > 2(2 - \sqrt{2})]$), the highest bid of $(1,1)$ is played in equilibrium.



\begin{align*}
& x = a_1\\
& y = \frac{a_2-a_1}{2}
\end{align*}
Two parameters $a_1$ and $a_3$ are needed to characterize equilibrium (By ... $a_2$ is half way between $a_1$ and $a_3$).
\begin{align*}
& u(a_1,(0,0)) = u(a_1,(1,0))\\
& u(a_3,(1,0)) = u(a_3,(1,1))
\end{align*}
The system reduces to one cubic equation in $a_1$.
For the root $(2 (2 - 2 g + Sqrt[-g^2 + g^3]))/(4 - 4 g + g^2)$, the solution is in the feasible range ($0<a_1<a_3<1$) for $2(2 - \sqrt{2})< \gamma < 2$

the root $(2 (2 - 2 g - Sqrt[-g^2 + g^3]))/(4 - 4 g + g^2)$, real value only for $1\le g$, negative for all $g$. (zero for $g=1$ but the corresponding $a_3=2$).

the root $a_1 = -(4./(-2 + g))$ - negative for $g>2$. above 1 for $0<g<2$



\begin{align*}
& a_1 [\frac{1}{2}x+y + \gamma\frac{1}{4}x] = a_1 [\frac{1}{2}y + \frac{1}{2} + \gamma(\frac{1}{4}y + \frac{1}{2}x)] - \frac{1}{2}(1-x-y)
\end{align*}



\section{Two Bidders}
Here, we consider a special case of the equations above for $n=2$.
\begin{multline*}
\Pr(W_\mu \cap W_\nu)=\sum_{x=0}^{1}\sum_{y=0}^{1-x}\sum_{z=0}^{1-x-y}{1 \choose x}{1-x \choose y}{1-x-y \choose z}\frac{1}{x+z+1}\frac{1}{y+z+1}\cdot\\
\Pr(B_{\mu} = b_{\mu} \cap B_{\nu} < b_{\nu})^x \Pr(B_{\mu} < b_{\mu} \cap B_{\nu} = b_{\nu})^y \Pr(B_{\mu} = b_{\mu} \cap B_{\nu} = b_{\nu})^z \Pr(B_{\mu} < b_{\mu} \cap B_{\nu} < b_{\nu})^{1-x-y-z}
\end{multline*} 
The three summations resolve to the following 4 combinations of $(x,y,z)$
\begin{align*}
& 0,0,0\\
& 0,0,1\\
& 0,1,0\\
& 1,0,0
\end{align*}
Expanding the equation we get
\begin{align*}
& \Pr(W_\mu \cap W_\nu)= \\
& \underbrace{F_{\mu\nu}(b_{\mu},b_{\nu})}_{0,0,0} + 
\underbrace{\frac{1}{4}f_{\mu\nu}(b_{\mu},b_{\nu})}_{0,0,1} + 
\underbrace{\frac{1}{2}[F_{\mu\nu}(b_{\mu},b_{\nu}+\epsilon) - F_{\mu\nu}(b_{\mu},b_{\nu})]}_{0,1,0} + 
\underbrace{\frac{1}{2}[F_{\mu\nu}(b_{\mu}+\epsilon,b_{\nu}) - F_{\mu\nu}(b_{\mu},b_{\nu})]}_{1,0,0} = \\
& \frac{1}{4}f_{\mu\nu}(b_{\mu},b_{\nu}) + \frac{1}{2}F_{\mu\nu}(b_{\mu},b_{\nu}+\epsilon) + \frac{1}{2}F_{\mu\nu}(b_{\mu}+\epsilon,b_{\nu})
\end{align*} 
%[F_{\mu\nu}(b_{\mu}+\epsilon,b_{\nu}) - F_{\mu\nu}(b_{\mu},b_{\nu})]^x [F_{\mu\nu}(b_{\mu},b_{\nu}+\epsilon) - F_{\mu\nu}(b_{\mu},b_{\nu})]^y f_{\mu\nu}(b_{\mu},b_{\nu})^z F_{\mu\nu}(b_{\mu},b_{\nu})^{n-1-x-y-z}


The other equations are simplified as follows
\begin{align*}
& \Pr(S_{\mu}) = F_{\mu}(b_{\mu})\\
& \Pr(S_{\mu\nu}) = F_{\mu\nu}(b)\\
& \Pr(T_{\mu}) = \frac{1}{2}f_{\mu}(b_{\mu})\\
& \Pr(W_{\mu}) = \Pr(S_{\mu}) + \Pr(T_{\mu})
\end{align*}


Specializing Equation~\ref{eq:ut} we get 
\begin{align*}
& u(\theta_i,b) = \theta_i \left(\alpha\Pr(W_{\mu}) + \beta\Pr(W_{\nu})  + (\gamma - \alpha -\beta)\Pr(W_{\mu} \cap W_{\nu}) \right) - c(b)\\
& = \theta_i (\alpha[F_{\mu}(b_{\mu}) + \frac{1}{2}f_{\mu}(b_{\mu})] + \beta[F_{\nu}(b_{\nu}) + \frac{1}{2}f_{\nu}(b_{\nu})] + \\
& (\gamma - \alpha -\beta)[\frac{1}{4}f_{\mu\nu}(b_{\mu},b_{\nu}) + \frac{1}{2}F_{\mu\nu}(b_{\mu},b_{\nu}+\epsilon) + \frac{1}{2}F_{\mu\nu}(b_{\mu}+\epsilon,b_{\nu})]) - c(b)
\end{align*}

The expected payment simplifies to
\begin{align*}
& c_{\mu}(b_{\mu}) = \left(\sum_{d \in B_{\mu} \mid d < b_{\mu}}f_{\mu}(d)d\right) + \frac{1}{2}f_{\mu}(b_{\mu})b_{\mu}\\
& c(b) = \left(\sum_{d \in B_{\mu} \mid d < b_{\mu}}f_{\mu}(d)d\right) + \frac{1}{2}f_{\mu}(b_{\mu})b_{\mu} + \left(\sum_{d \in B_{\nu} \mid d < b_{\nu}}f_{\nu}(d)d\right) + \frac{1}{2}f_{\nu}(b_{\nu})b_{\nu}
\end{align*}









\subsection{Two Bids}
Further assume the only available bids are $0$ and $1$. There are 4 possible bid pairs. We denote the probability of submitting each bid pair below
\begin{align*}
%even &'s separate columns
& f_{\mu\nu}(0,0) = x       &   F_{\mu\nu}(0,0) =0\\
& f_{\mu\nu}(1,0) = y       &   F_{\mu\nu}(1,0) =0\\
& f_{\mu\nu}(0,1) = z       &   F_{\mu\nu}(0,1) =0\\
& f_{\mu\nu}(1,1) = 1-x-y-z &   F_{\mu\nu}(1,1) =x
\end{align*}
The corresponding  marginal distributions are
\begin{align*}
& f_{\mu}(0) = x+z   & & F_{\mu}(0) = 0    & & f_{\nu}(0) = x+y    & & F_{\nu}(0) = 0\\
& f_{\mu}(1) = 1-x-z & & F_{\mu}(1) = x+z  & & f_{\nu}(1) = 1-x-y  & & F_{\nu}(1) = x+y
\end{align*}



Using the equations below 
\begin{align*}
& u(\theta_i,b) = \theta_i (\alpha[F_{\mu}(b_{\mu}) + \frac{1}{2}f_{\mu}(b_{\mu})] + \beta[F_{\nu}(b_{\nu}) + \frac{1}{2}f_{\nu}(b_{\nu})] + \\
& (\gamma - \alpha -\beta)[\frac{1}{4}f_{\mu\nu}(b_{\mu},b_{\nu}) + \frac{1}{2}F_{\mu\nu}(b_{\mu},b_{\nu}+\epsilon) + \frac{1}{2}F_{\mu\nu}(b_{\mu}+\epsilon,b_{\nu})]) - c(b)\\
& c(b) = \left(\sum_{\beta \in B_{\mu} \mid \beta < b_{\mu}}f_{\mu}(\beta)\beta\right) + \frac{1}{2}f_{\mu}(b_{\mu})b_{\mu} + \left(\sum_{\beta \in B_{\nu} \mid \beta < b_{\nu}}f_{\nu}(\beta)\beta\right) + \frac{1}{2}f_{\nu}(b_{\nu})b_{\nu}
\end{align*}
we calculate the utility of submitting each bid pair
%%%use these equations
\begin{align*}
& u(\theta_i,(0,0)) = \theta_i [\alpha\frac{1}{2}(x+z) + \beta\frac{1}{2}(x+y) + (\gamma - \alpha -\beta)\frac{1}{4}x] = \theta_i [\alpha(\frac{1}{4}x+\frac{1}{2}z) + \beta(\frac{1}{4}x+\frac{1}{2}y) + \gamma\frac{1}{4}x]\\
& u(\theta_i,(1,0)) = \theta_i [\alpha(x+z + \frac{1}{2}(1-x-z)) + \beta\frac{1}{2}(x+y) + (\gamma - \alpha -\beta)(\frac{1}{4}y + \frac{1}{2}x)] - \frac{1}{2}(1-x-z) = \\
&  \quad \theta_i [\alpha(- \frac{1}{4}y + \frac{1}{2}z + \frac{1}{2}) + \beta\frac{1}{4}y + \gamma(\frac{1}{4}y + \frac{1}{2}x)] - \frac{1}{2}(1-x-z)\\
& u(\theta_i,(0,1)) = \theta_i [\alpha\frac{1}{2}(x+z) + \beta(x+y + \frac{1}{2}(1-x-y)) + (\gamma - \alpha -\beta)(\frac{1}{4}z + \frac{1}{2}x)] - \frac{1}{2}(1-x-y) =\\
&  \quad \theta_i [\alpha\frac{1}{4}z + \beta(\frac{1}{2}y -\frac{1}{4}z + \frac{1}{2}) + \gamma(\frac{1}{4}z + \frac{1}{2}x)] - \frac{1}{2}(1-x-y)\\
%this is one is correct, just not simplified. see appendix.tex
& u(\theta_i,(1,1)) = \theta_i [\alpha(x + z + \frac{1}{2}(1 - x - z)) + \beta(x+y + \frac{1}{2}(1-x-y)) + \\
& \quad (\gamma - \alpha -\beta)(\frac{1}{4}(1-x-y-z) + \frac{1}{2}(x + z) + \frac{1}{2}(x + y))] - \frac{1}{2}(1-x-y) - \frac{1}{2}(1-x-z) =\\
\end{align*}

Simplified equations
\begin{align*}
& u(0,0) = \frac{(2a_2 + g a_1)t}{4} 
\end{align*}

\begin{align*}
& u(\theta_i,(0,0)) = \theta_i [\alpha(\frac{1}{4}x+\frac{1}{2}z) + \beta(\frac{1}{4}x+\frac{1}{2}y) + \gamma\frac{1}{4}x] \\
& u(\theta_i,(1,0)) = \theta_i [\alpha(- \frac{1}{4}y + \frac{1}{2}z + \frac{1}{2}) + \beta\frac{1}{4}y + \gamma(\frac{1}{4}y + \frac{1}{2}x)] - \frac{1}{2}(1-x-z)\\
& u(\theta_i,(0,1)) = \theta_i [\alpha\frac{1}{4}z + \beta(\frac{1}{2}y -\frac{1}{4}z + \frac{1}{2}) + \gamma(\frac{1}{4}z + \frac{1}{2}x)] - \frac{1}{2}(1-x-y)\\
& u(\theta_i,(1,1)) = see appendix.tex
\end{align*}



Recalling the characterization in Section~\ref{sec:char}, we search for an equilibrium for all ordering of bids.


The following demonstrates that the slope of the bid $(0,0)$ is lower than the one of the bid $(1,0)$
\begin{align*}
& \underbrace{\alpha(- \frac{1}{4}y + \frac{1}{2}z + \frac{1}{2}) + \beta\frac{1}{4}y + \gamma(\frac{1}{4}y + \frac{1}{2}x)}_{\text{slope of $(1,0)$}} - (\underbrace{\alpha(\frac{1}{4}x+\frac{1}{2}z) + \beta(\frac{1}{4}x+\frac{1}{2}y) + \gamma\frac{1}{4}x}_{\text{slope of $(0,0)$}})  = \\
& \alpha(-\frac{1}{4}x - \frac{1}{4}y + \frac{1}{2}) + \beta(-\frac{1}{4}x -\frac{1}{4}y) + \gamma(\frac{1}{4}x + \frac{1}{4}y) = \\
& \frac{1}{4}(\gamma - \alpha - \beta)(x+y) + \frac{1}{2}\alpha \ge && \text{by free disposal $\gamma \ge \beta$}\\
& \frac{1}{4}((- \alpha)(x+y) + 2\alpha) \ge && \text{by definition $x + y \le 1$}\\
& \frac{1}{4}\alpha \ge 0
\end{align*}
Carrying out the same calculation for $(0,0)$ and $(0,1)$, we obtain
\begin{align*}
& \underbrace{\alpha\frac{1}{4}z + \beta(\frac{1}{2}y -\frac{1}{4}z + \frac{1}{2}) + \gamma(\frac{1}{4}z + \frac{1}{2}x)}_{\text{slope of $(0,1)$}} - (\underbrace{\alpha(\frac{1}{4}x+\frac{1}{2}z) + \beta(\frac{1}{4}x+\frac{1}{2}y) + \gamma\frac{1}{4}x}_{\text{slope of $(0,0)$}})  = \\
& \alpha(-\frac{1}{4}x - \frac{1}{4}z) + \beta(-\frac{1}{4}x -\frac{1}{4}z + \frac{1}{2}) + \gamma(\frac{1}{4}x + \frac{1}{4}z) = \\
& \frac{1}{4}(\gamma - \alpha - \beta)(x+z) + \frac{1}{2}\beta \ge && \text{by free disposal $\gamma \ge \alpha$}\\
& \frac{1}{4}((- \beta)(x+z) + 2\beta)\ge && \text{by definition $x + z \le 1$}\\
& \frac{1}{4}\beta \ge 0
\end{align*}


Next, we compare  slopes of the bids $(1,0)$ and $(0,1)$.
The slope of the bid $(0,1)$ is larger than the slope of the bid $(1,0)$ when
\begin{align*}
& \alpha(- \frac{1}{4}y + \frac{1}{2}z + \frac{1}{2}) + \beta\frac{1}{4}y + \gamma(\frac{1}{4}y + \frac{1}{2}x) \le \alpha\frac{1}{4}z + \beta(\frac{1}{2}y -\frac{1}{4}z + \frac{1}{2}) + \gamma(\frac{1}{4}z + \frac{1}{2}x)\\
& \alpha(\frac{1}{2}- \frac{1}{4}y + \frac{1}{4}z) - \beta(\frac{1}{2} + \frac{1}{4}y -\frac{1}{4}z) + \gamma(\frac{1}{4}y - \frac{1}{4}z) \le 0\\
& \alpha(2- y + z) - \beta(2 + y -z) + \gamma(y - z) \le 0\\
& 2\alpha - 2\beta - (\alpha+\beta)(y - z)  + \gamma(y - z) \le 0\\
& 2(\beta-\alpha) - (\alpha+\beta)(z - y)  + \gamma(z - y) \ge 0\\
& 2(\beta-\alpha) + (\gamma - \alpha-\beta)(z - y)  \ge 0
%& \gamma \ge (\alpha+\beta) -\frac{2(\beta-\alpha)}{z-y} \\
\end{align*}
Without loss of generality assume the second items is more valuable than the first: $\beta > \alpha$.

There are two possible orderings of slopes $(0,0)$, $(1,0)$, $(0,1)$, $(1,1)$ and $(0,0)$, $(0,1)$, $(1,0)$, $(1,1)$. Consider two corresponding cases.

{\bf Case 1.} $2(\beta-\alpha) + (\gamma - \alpha-\beta)(z - y)  \ge 0$
The constrants for the equilibrium strategy given this ordering are
\begin{align*}
& a_1 = v \mid u(0,0) = u(0,1)\\
& a_2 = v \mid u(0,1) = u(1,0)\\
& a_3 = v \mid u(1,0) = u(1,1)
\end{align*}
Using Observation~\ref{obs:mon}, the equilibrium is a solution $0 \le x_1,\ldots,x_m \le 1$ to the system of equations
\begin{align*}
& a_i - a_{i-1} =  x_i
\end{align*}
The solution must satisfy
\begin{align*}
2(\beta-\alpha) + (\gamma - \alpha-\beta)(z - y)  \ge 0
\end{align*}

\commentv{solve a system of equations - implement in cplex?}


%\begin{lemma}
%When the second item is more valuable than the first, in equilibrium $z \ge y$.
%\end{lemma}
%\commentv{prove this}
%In words, this holds for all complementarity levels stronger than a little below the additive valuations and we have a full order of slopes: $(0,0)$, $(1,0)$, $(0,1)$, and $(1,1)$.
As mentioned earlier, the best bid when the value is zero is $(0,0)$. It remains optimal as the value is increased until another bid becomes optimal. We check which of the other bids becomes optimal next. For ease of notation, we use $v$ instead of $\theta_i$.
\begin{align*}
& u(0,0) = u(1,0) && v = \frac{1-x-z}{\frac{1}{2}(\gamma - \alpha - \beta)(x+y) + \alpha }\\
& u(0,0) = u(0,1) && v = \frac{1-x-y}{\frac{1}{2}(\gamma - \alpha - \beta)(x+z) + \beta}\\
\end{align*}
%\begin{conjecture}
%Based on computational results we conjecture that when $\beta > \alpha$ and goods are close to perfect substitutes, the unique equilibrium is to bid $(1,0)$ and then $(0,1)$.
%\end{conjecture}

\subsection{Non-Identical Auctions}






\subsubsection{Equilibrium for $\gamma = \beta = 4\alpha=1$}

We simplify the utility equations
\begin{align*}
& u(\theta_i,(0,0)) = \theta_i [\alpha(\frac{1}{4}x+\frac{1}{2}z) + \alpha x+2\alpha y + \alpha x]\\
& u(\theta_i,(1,0)) = \theta_i [\alpha(- \frac{1}{4}y + \frac{1}{2}z + \frac{1}{2}) + \alpha y + \alpha y + 2 \alpha x] - \frac{1}{2}(1-x-z)\\
& u(\theta_i,(0,1)) = \theta_i [\alpha\frac{1}{4}z + 2 \alpha y -\alpha z + 2\alpha + \alpha z + 2\alpha x)] - \frac{1}{2}(1-x-y)\\
& u(\theta_i,(1,1)) = see appendix.tex
\end{align*}

Plugging in $\alpha =.25$ and simplifying obtain
\begin{align*}
& u(v,(0,0)) = v*(0.5625*x + 0.5*y + 0.125*z)\\
& u(v,(1,0)) = 0.5*x + 0.5*z + v*(0.5*x + 0.4375*y + 0.125*z + 0.125) - 0.5\\
& u(v,(0,1)) = 0.5*x + 0.5*y + v*(0.5*x + 0.5*y + 0.0625*z + 0.5) - 0.5\\
& u(v,(1,1)) = x + 0.5*y + 0.5*z + v*(0.4375*x + 0.5625*y + 0.1875*z + 0.5625) - 1
\end{align*}


We consider all possible cases exhuastively. There are two possible orderings of slopes: $(0,0), (1,0), (0,1), (1,1)$ and $(0,0), (0,0), (1,0), (1,1)$. 
For a given ordering the equilibrium is characterized by Lemma~\ref{obs:mon}.





\begin{align*}
& u(0,0) = u(1,0) && v = \frac{1-x-z}{\frac{1}{2}(- \alpha)(x+y) + \alpha} = \frac{2(1-x-z)}{\alpha(2-x-y)}\\
& u(0,0) = u(0,1) && v = \frac{1-x-y}{\frac{1}{2}(- \alpha)(x+z) + 4\alpha} = \frac{2(1-x-y)}{\alpha(8-x-z)}\\
\end{align*}

{\bf case 1: $\frac{1-x-z}{\frac{1}{2}(- \alpha)(x+y) + \alpha } < \frac{1-x-y}{\frac{1}{2}(- \alpha)(x+z) + 4\alpha}$}
\begin{align*}
& \frac{2(1-x-z)}{\alpha(2-x-y)} < \frac{2(1-x-y)}{\alpha(8-x-z)}\\
& \frac{(1-x-z)}{(2-x-y)} < \frac{(1-x-y)}{(8-x-z)}\\
\end{align*}


10 = 01
\begin{align*}
& u(\theta_i,(1,0)) = v[\alpha(- \frac{1}{4}y + \frac{1}{2}z + \frac{1}{2}) + \beta\frac{1}{4}y + \gamma(\frac{1}{4}y + \frac{1}{2}x)] - \frac{1}{2}(1-x-z)\\
& \quad = v[\alpha(- \frac{1}{4}y + \frac{1}{2}z + \frac{1}{2}) + \alpha y + \alpha y + 2\alpha x)] - \frac{1}{2}(1-x-z)\\
& \quad = v[\alpha(2x + \frac{7}{4}y + \frac{1}{2}z + \frac{1}{2})] - \frac{1}{2}(1-x-z)\\
& u(\theta_i,(0,1)) = v[\alpha\frac{1}{4}z + \beta(\frac{1}{2}y -\frac{1}{4}z + \frac{1}{2}) + \gamma(\frac{1}{4}z + \frac{1}{2}x)] - \frac{1}{2}(1-x-y)\\
& \quad = v[\alpha\frac{1}{4}z + \alpha(2y - z + 2) + \alpha(z + 2x)] - \frac{1}{2}(1-x-y)\\
& \quad = v[\alpha(2x + 2y + \frac{1}{4}z + 2)] - \frac{1}{2}(1-x-y)\\
&\quad \\
& v[\alpha(2x + \frac{7}{4}y + \frac{1}{2}z + \frac{1}{2})] - \frac{1}{2}(1-x-z)= v[\alpha(2x + 2y + \frac{1}{4}z + 2)] - \frac{1}{2}(1-x-y)\\
& v[\alpha(\frac{1}{4}y - \frac{1}{4}z + \frac{3}{2})] = \frac{z-y}{2}\\
& v = \frac{z-y}{\alpha(\frac{1}{2}y - \frac{1}{2}z + 3)}\\
\end{align*}


01 = 11


An equilibrium must satisfy
\begin{align*}
\begin{cases}
\frac{2(1-x-z)}{\alpha(2-x-y)} = x\\
\frac{z-y}{\alpha(\frac{1}{2}y - \frac{1}{2}z + 3)} = x + y\\
1 = x + y + z
\end{cases}
\end{align*}

Plugging in $z = 1-x-y$ into the first 2 equations we obtain
\begin{align*}
&\begin{cases}
\frac{2y}{\alpha(2-x-y)} = x\\
\frac{1-x-2y}{\alpha(3-\frac{1}{2}(1 -x -2y))} = x + y
\end{cases}\\
&2y = \alpha(2-x-y)x = \alpha x(2-x) - \alpha xy\\
&y = \frac{\alpha x(2-x)}{2+\alpha x}
& \ldots \text{then it gets ugly}
\end{align*}


Next, we plug in $\alpha = .25$, express equations as one cubic equation in $x$ and obtain three roots in Mupad.
\begin{align}
& y = (.25*x*(2-x)/(2+.25*x))\\
& (1-x-2*(.25*x*(2-x)/(2+.25*x)))/(.25*(3 - .5*(1-x-2*(.25*x*(2-x)/(2+.25*x)))))\\
& = x+(.25*x*(2-x)/(2+.25*x)\\
& [x = 0.4552759936], [x = 14.60137143], [x = -4.278869648]
\end{align}
The only solution between $0$ and $1$ is $x = 0.4552759936$. The corresponding values of the other probabilities are $y = 0.08317596698$ and $z=0.4615480394$.


\commentv{Zinovi, can you describe again why the system is guaranteed to have a solution? Is the solution unique?}

\commentv{figure out why 1,1 is never played}


\subsection{Identical Auctions}
When identical items are sold in all auctions, the marginal distribution of equilibrium bids must be the same.
\commentv{formalize and prove}


Observe that if $y>0$, then in equilibrium $z=y$: if one of the symmetric bids $(1,0)$ or $(0,1)$ is played, the other one must be played with the same probability. If this is not the case, the best response would be to put more mass on the bid that is played less often. When $y=z$, utilities from bids $(1,0)$ and $(0,1)$ are the same. Either bid can replace $(0,0)$ as the best response for $v \ge a_1$ for some $a_1 \in (0,1]$. The bids $(1,0)$ and $(0,1)$ are played until $(1,1)$ becomes the best response for all values above some $a_2 > a_1$. The equilibrium must satisfy $y=z =\frac{a_2-a_1}{2}$. Formally, any strategy of the form shown in Figure~\ref{fig:iaeq} is an equilibrium.
\boxedfig{
\begin{align*}
& s(v) = (0,0) && \text{if } v \in [0,a_1)\\
& s(v) = (0,1) \text{ or } (1,0) \mid f(1,0) = f(0,1) = \frac{a_2-a_1}{2} && \text{if } v \in [a_1,a_2]\\
& s(v) = (1,1) && \text{if } v \in (a_2,1]\\
\end{align*}
\caption{Identical Auctions Equilibrium}
\label{fig:iaeq}
}
The simplest equilibrium of this form is the one switching from $(1,0)$ to $(0,1)$ halfway between $a_1$ and $a_2$.

In the case of symmetric auctions, the order of slopes of bids for all complementarity parameters is the same: $(0,0)$ has the smaller slope, followed by $(1,0)$ and $(0,1)$ that have the same slope, and $(1,1)$ with the highest slope. Another observation is that in equilibrium, the bid $(0,0)$ is played with a positive probability. These two observations imply that ther are three possible sets of bids that may consititute an equilibrium: the bid $(0,0)$ by itself, the bids $(0,0)$, $(1,0)$, $(0,1)$, and all bids.

For given complementarity parameters, we can find the equlibrium by solving

degrees of freedom:
 value of the more expensive item
 complementarity structure
??? should we fix the value of the more expensive item at 1? - yes, will still bid (1,1) when items are complementary


\begin{theorem}
The equilibrium is unique
\end{theorem}
\begin{proof}
show that out of all possible envelopes, only one can have a solution and it is either x,y,z or x,y,z,w
interesting case to prove: x,w does not have a solution
simple case: x>0

\end{proof}

show uniqueness


characterize equilibrium exactly - find a and b!!!


Equilibrium when auctions are almost identical approaches the identical one: i.e., as value of the goods become closer so do the probabilities of playing $(1,0)$ and $(0,1)$.




\newpage
%\commentv{Once we go through all envelopes we'll be able to talk about uniqueness.}



the root $x= \frac{-4 - a + \sqrt{16a + a^2}}{-4 + 2a}$\\
$x=1$ when $\gamma=0$, 
$x=0$ when $\gamma=\infty$.

The correspoding $y$ is
\begin{align*}
& y = \frac{1-x}{2} = \frac{-4 - a + \sqrt{16a + a^2}}{-4 + 2a}
\end{align*}

However not all solution may be equilibrium solutions. For a solution to be equilibrium the bid $(1,1)$ must never yield the highest utility across bids. 


insert plot $zs$ u(0,1) - u(1,1) as a function of $a$ - straight line. understand why.

Got the point where (1,1) becomes the best response. The point is $2(2-\sqrt{2}) = 1.17157$. How does calculation of the point where 1,0 takes over 0,0 change when the last bid is played (i.e., $x+2y<0$).



A family of parabolas $x^2(\gamma - 2) + x(\gamma + 4) - 2 = 0$ for $0 \le \gamma \le 4$ appears in Figure~\ref{fig:zeroone0}. Most of the have a root between zero and one. We zoom in on the region in Figure~\ref{fig:zeroone1}.


\begin{figure}
\begin{center}
\includegraphics[width=14cm]{graphs/zeroone0}
\end{center}
\label{fig:zeroone0}
\caption{Parabolas for $0 \le \gamma \le 4$.}
\end{figure}


\begin{figure}
\begin{center}
\includegraphics[width=14cm]{graphs/zeroone1}
\end{center}
\label{fig:zeroone1}
\caption{Parabolas for $0 \le \gamma \le 4$ in the zero-one region.}
\end{figure}



The items are complements for $a>2$, in which case the parabola is upward facing. For $a<2$, the items are substitutes, and the parabola is downward facing. For $a=2$, the items are independent and a graph of the equation is a straight line.






Now we consider the case when $(1,1)$ is played with positive probability.

\begin{align*}
& x = a\\
& y = z = \frac{b-a}{2}
\end{align*}
Which implies
\begin{align*}
& x+y+z = x+2y = b
\end{align*}

Assuming $0< a \neq b <1$, the parameters $a=x$ and $b=x+y+z=x+2y$ are determined by solutions to the system of 2 equations
\begin{align*}
& u(x,(0,0)) = u(x,(1,0))\\
& u(x+2y,(1,0)) = u(x+2y,(1,1))
\end{align*}

Expanding the first equation and solving for $y$, we get
\begin{align*}
& x [\alpha(\frac{1}{4}x+\frac{1}{2}y) + \beta(\frac{1}{4}x+\frac{1}{2}y) + \gamma\frac{1}{4}x] = x [\alpha(\frac{1}{4}y + \frac{1}{2}) + \beta\frac{1}{4}y + \gamma(\frac{1}{4}y + \frac{1}{2}x)] - \frac{1}{2}(1-x-y)\\
&  \frac{x^2\alpha}{4}+\frac{xy \alpha}{2} + \frac{x^2\beta}{4}+\frac{xy\beta}{2} + \frac{x^2\gamma}{4} = \frac{xy\alpha}{4} + \frac{x\alpha}{2} +\frac{xy\beta}{4} + \frac{xy\gamma}{4} + \frac{x^2\gamma}{2} - \frac{1}{2} + \frac{x}{2} + \frac{y}{2}\\
&  x^2\alpha+2xy \alpha + x^2\beta+2xy\beta+ x^2\gamma = xy\alpha + 2x\alpha +xy\beta + xy\gamma + 2x^2\gamma - 2 + 2x + 2y\\
&  y = \frac{x^2\alpha+ x^2\beta + x^2\gamma - 2x\alpha - 2x^2\gamma + 2 - 2x}{-2x\alpha - 2x\beta + x\alpha + x\beta + x\gamma +2}
\end{align*}
Next we plug in $y$ into the second equation $u(x+2y,(1,0)) = u(x+2y,(1,1))$
\begin{align*}
& (x+2y)[\alpha(\frac{1}{4}y + \frac{1}{2}) + \beta\frac{1}{4}y + \gamma(\frac{1}{4}y + \frac{1}{2}x)] - \frac{1}{2}(1-x-y)  \\
& = (x+2y)[\alpha(-\frac{1}{4}x+y + \frac{1}{4}) + \beta(-\frac{1}{4}x + y + \frac{1}{4}) + \gamma(\frac{3}{4}x -\frac{1}{2}y + \frac{1}{4})] - 1 + x + y
\end{align*}



g=2 is a special value!! many terms (including quadratic) cancel out - get a line.


\begin{align*}
&  y = \frac{2x^2 - 4x- x^2c + 2}{-2x+  xc +2}\\
& (x+y) [\frac{1}{2}y + \frac{1}{2} + c(\frac{1}{4}y + \frac{1}{2}x)] - \frac{1}{2}(1-x-y) = (x+y)[-\frac{1}{2}x+ 2y + \frac{1}{2} + c(\frac{3}{4}x -\frac{1}{2}y + \frac{1}{4})] - 1 + x + y
\end{align*}

The equation expressing $y$ is quadratic in $x$. The second equation has $y^2$ terms, so a priory, it can be 4th degree in x. Luckily, notice that 
\begin{align*}
&  x+y = \frac{-2x + 2}{-2x+  xc +2}\\
\end{align*}
\commentv{wrong! it's $x+2y$ and the quadratic term in the numerator does not cancel out.}

and plug it into the second equation
\begin{align*}
& \frac{-2x + 2}{-2x+  xc +2} [\frac{1}{2}y + \frac{1}{2} + c(\frac{1}{4}y + \frac{1}{2}x)] - \frac{1}{2}(1-x-y) = \frac{-2x + 2}{-2x+  xc +2}[-\frac{1}{2}x+ 2y + \frac{1}{2} + c(\frac{3}{4}x -\frac{1}{2}y + \frac{1}{4})] - 1 + x + y
\end{align*}
The equation is cubic in $x$ as will be obvious after a few manipulations.
Further, plugging in $y$ we get
\begin{align*}
& \frac{-2x + 2}{-2x+  xc +2} [\frac{1}{2}\frac{2x^2 - 4x- x^2c + 2}{-2x+  xc +2} + \frac{1}{2} + c(\frac{1}{4}\frac{2x^2 - 4x- x^2c + 2}{-2x+  xc +2} + \frac{1}{2}x)] - \frac{1}{2}(1-x-\frac{2x^2 - 4x- x^2c + 2}{-2x+  xc +2}) \\
& = \frac{-2x + 2}{-2x+  xc +2}[-\frac{1}{2}x+ 2\frac{2x^2 - 4x- x^2c + 2}{-2x+  xc +2} + \frac{1}{2} + c(\frac{3}{4}x -\frac{1}{2}\frac{2x^2 - 4x- x^2c + 2}{-2x+  xc +2} + \frac{1}{4})] - 1 + x + \frac{2x^2 - 4x- x^2c + 2}{-2x+  xc +2}
\end{align*}
Multiple both sides by $(-2x+  xc +2)^2$
\begin{align*}
& \frac{1}{2}(-2x + 2)(2x^2 - 4x- x^2c + 2) + \frac{1}{2}(-2x + 2)(-2x+  xc +2) + c\frac{1}{4}(-2x + 2)(2x^2 - 4x- x^2c + 2) \\
& + c\frac{1}{2}x(-2x + 2)(-2x+  xc +2) - \frac{1}{2}(-2x+  xc +2)^2  + \frac{1}{2}x(-2x+  xc +2)^2+\frac{1}{2}(2x^2 - 4x- x^2c + 2)(-2x+  xc +2) \\
& = -\frac{1}{2}(-2x + 2)(-2x+  xc +2)x+ 2(2x^2 - 4x- x^2c + 2)(-2x+2) + \frac{1}{2}(-2x + 2)(-2x+  xc +2) \\
& + c(\frac{3}{4}x(-2x+2)(-2x+  xc +2) -c\frac{1}{2}(2x^2 - 4x- x^2c + 2)(-2x+2) + c\frac{1}{4}(-2x+2)(-2x+  xc +2) \\
& - (-2x+  xc +2)^2 + x(-2x+  xc +2)^2 + (2x^2 - 4x- x^2c + 2)(-2x+  xc +2)
\end{align*}
This is just a long cubic equation.



\end{document}
